import libnum
from Crypto.Util.number import *

e = 0x10001
c = 0x3862c872480bdd067c0c68cfee4527a063166620c97cca4c99baff6eb0cf5d42421b8f8d8300df5f8c7663adb5d21b47c8cb4ca5aab892006d7d44a1c5b5f5242d88c6e325064adf9b969c7dfc52a034495fe67b5424e1678ca4332d59225855b7a9cb42db2b1db95a90ab6834395397e305078c5baff78c4b7252d7966365afed9e
n = 0x118aaa1add80bdd0a1788b375e6b04426c50bb3f9cae0b173b382e3723fc858ce7932fb499cd92f5f675d4a2b05d2c575fc685f6cf08a490d6c6a8a6741e8be4572adfcba233da791ccc0aee033677b72788d57004a776909f6d699a0164af514728431b5aed704b289719f09d591f5c1f9d2ed36a58448a9d57567bd232702e9b28f
roots = [(
    6813140671672694477701511883397067876211159809088064490593325584756562268820329988116480298456252746748095410666300132267213094431909630229631434972416225885,
    1), (
    4573744216059593260686660411936793507327994800883645562370166075007970317346237399760397301505506131100113886281839847419425482918932436139080837246914736557,
    1), (
    1859314969084523636298100850823722544590555574470838518640063093117116629078281861281849586432508721074855657736668366212762253040197962779753163192386773060,
    1)]
for i in roots:
    if libnum.gcd(int(i[0]), n) != 1:
        p = i[0]
        q = n // p
        phi = (p - 1) * (q - 1)
        d = libnum.invmod(e, phi)
        m = pow(c, d, n)
        print(long_to_bytes(m))
